package com.sukaiyi.leetcode._98validate_binary_search_tree;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author sukaiyi
 * @date 2020/05/06
 * @see <a href="https://leetcode-cn.com/problems/validate-binary-search-tree/>题目地址</a>
 */
public class Solution {

    @Test
    public void test() {
        TreeNode treeNode = new TreeNode(2);
        treeNode.left = new TreeNode(1);
        treeNode.right = new TreeNode(3);
        Assertions.assertTrue(isValidBST(treeNode));

        treeNode = new TreeNode(5);
        treeNode.left = new TreeNode(1);
        treeNode.right = new TreeNode(4);
        treeNode.right.left = new TreeNode(3);
        treeNode.right.right = new TreeNode(6);
        Assertions.assertFalse(isValidBST(treeNode));

        treeNode = new TreeNode(10);
        treeNode.left = new TreeNode(5);
        treeNode.right = new TreeNode(15);
        treeNode.right.left = new TreeNode(6);
        treeNode.right.right = new TreeNode(20);
        Assertions.assertFalse(isValidBST(treeNode));
    }

    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, new HashMap<>());
    }

    private boolean isValidBST(TreeNode root, Map<TreeNode, Integer> table) {
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left, table)) {
            return false;
        }
        if (!isValidBST(root.right, table)) {
            return false;
        }
        return (root.left == null || root.left.val < root.val) && (root.right == null || root.right.val > root.val);
    }


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

}
